package org.example.myleet.p417;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class Solution {

    private static final int[][] DIRECTIONS = new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        int m = heights.length, n = heights[0].length, me = m - 1, ne = n - 1;
        int[][] pacificFlow = new int[m][n];
        int[][] atlanticFlow = new int[m][n];
        Deque<int[]> stack = new LinkedList<>();
        //遍历4条边的位置，通过BFS反向找到可以流入到太平洋和大西洋的位置，最后再遍历一次矩阵以知道是否可以同时到达两个大洋
        for (int i = 0; i < m; ++i) {
            if (pacificFlow[i][0] < 1) {
                pacificFlow[i][0] = 1;
                stack.offer(new int[]{i, 0});
                bfs(stack, heights, m, n, pacificFlow);
            }
        }
        for (int j = 1; j < n; ++j) {
            if (pacificFlow[0][j] < 1) {
                pacificFlow[0][j] = 1;
                stack.offer(new int[]{0, j});
                bfs(stack, heights, m, n, pacificFlow);
            }
        }
        for (int i = 0; i < m; ++i) {
            if (atlanticFlow[i][ne] < 1) {
                atlanticFlow[i][ne] = 1;
                stack.offer(new int[]{i, ne});
                bfs(stack, heights, m, n, atlanticFlow);
            }
        }
        for (int j = 0; j < ne; ++j) {
            if (atlanticFlow[me][j] < 1) {
                atlanticFlow[me][j] = 1;
                stack.offer(new int[]{me, j});
                bfs(stack, heights, m, n, atlanticFlow);
            }
        }
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (pacificFlow[i][j] == 1 && atlanticFlow[i][j] == 1) {
                    ArrayList<Integer> p = new ArrayList<>(2);
                    p.add(i);
                    p.add(j);
                    result.add(p);
                }
            }
        }
        return result;
    }

    private void bfs(Deque<int[]> stack, int[][] heights, int m, int n, int[][] oceanFlow) {
        while (!stack.isEmpty()) {
            int size = stack.size();
            for (int i = 0; i < size; ++i) {
                int[] p = stack.poll();
                for (int j = 0; j < 4; ++j) {
                    int nr = p[0] + DIRECTIONS[j][0];
                    int nc = p[1] + DIRECTIONS[j][1];
                    if (0 <= nr && nr < m && 0 <= nc && nc < n) {
                        if (heights[nr][nc] >= heights[p[0]][p[1]] && oceanFlow[nr][nc] < 1) {
                            oceanFlow[nr][nc] = 1;
                            int[] np = new int[]{nr, nc};
                            stack.offer(np);
                        }
                    }
                }
            }
        }
    }
}
